﻿#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int rectCover(int number)
    {
        if (number == 0)
        {
            return 0;
        }
        int* dp = new int[number + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= number; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        int num = dp[number];
        delete[] dp;
        return num;
    }
};

/*
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

数据范围：0≤n≤38
进阶：空间复杂度O(1)  ，时间复杂度O(n)

注意：约定 n == 0 时，输出 0

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

输入描述：
2*1的小矩形的总个数n
返回值描述：
覆盖一个2*n的大矩形总共有多少种不同的方法(从同一个方向看)
*/

/*
状态定义：f(n) : 用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形所用的总方法数
状态递推：f(n) = f(n-1)【最后一个竖着放】 + f(n-2)【最后两个横着放】
初始化：f(1) = 1,f(2) = 2,f(0)=1

状态递归方程由来：现在有n个小矩阵，相比n-1个小矩阵，多了一个，并且这一个只能竖着放，所以跟n-1放法相同
                  现在有n个小矩阵，相比n-2个小矩阵，多了两个，并且只两个只能合并横着放，所以跟n-2方法相同
两者相加即可得到结果
*/

